package own.stu.jobgib.playown.alg.leetcode.editor.cn;

/**
 * 描述
 * 给出一个整数数组 nums 和一个整数 k。划分数组（即移动数组 nums 中的元素），使得：
 *
 * 所有小于k的元素移到左边
 * 所有大于等于k的元素移到右边
 * 返回数组划分的位置，即数组中第一个位置 i，满足 nums[i] 大于等于 k。
 *
 * nums = [3,2,2,1]
 * k = 2
 */
public class PartitionArray {

    public static void main(String[] args) {
        System.out.println(partitionArray(new int[]{3,8,9,6,2,1}, 4));
    }
    /**
     * @param nums: The integer array you should partition
     * @param k: An integer
     * @return: The index after partition
     */
    public static int partitionArray(int[] nums, int k) {
        // write your code here
        if(nums == null || nums.length <= 0){
            return 0;
        }

        int n = nums.length;
        int i = -1;
        int j = 0;
        for(; j < n; j ++){
            if(nums[j] < k){
                if(i == -1 || nums[j - 1] > nums[j])
                    i ++;
                else{
                    swap(nums, j, ++i);
                }
            }
        }

        return i + 1;
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
